package com.fs.leetcode.paixu;

import java.util.Arrays;

/**
 * @author ：hyq
 * @date ：Created in 2020/6/11 16:35
 * @description：
 * @modified By：
 */
public class HeapSort {

    private static void swap(int[] tree, int n, int i) {
        int temp = tree[i];
        tree[i] = tree[n];
        tree[n] = temp;
    }
    //构建交换函数
    //n:代表有几个节点排序阶段需要不断的缩小需要最大值和之小值交换的范围， i: 对每个数进行 heapify
    public static void heapify(int tree[],int n,int i){
        //构建最大数 从哪个位置开始
         int max = i;
         int left = 2*i + 1;
         int right = 2*i + 1;

         if (left < n && tree[max] < tree[left]) {
             max =left;
         }

         if (right < n && tree[max] < tree[right]) {
             max = right;
         }

         //max 不是 我们设置的 i 需要交换位置
        if(max != i){
             swap(tree,n,i);
            heapify(tree,n,i);
        }
    }

    /**
     * 构建一个大顶堆将每个元素进行 heapify 操作
     * 从倒数第二层开始，从下往上开始构建
     * 找到堆中最后一个索引，最后一个索引的父节点就是倒数第二层
     */

    public static void buildheap(int tree[]){
        int lastindex = tree.length-1;

        int parent = (lastindex -1 ) / 2;

        for(int i = parent;i>=0;i--){
            heapify(tree,tree.length,i);
        }
    }

    //构建大顶堆后 交换最大值和最小值，重新构建大顶堆，然后逐渐缩小范围
    public static void HeapSort(int tree[]) {
        buildheap(tree);
        for (int i = tree.length - 1; i >= 0; i--) {
            swap(tree, i, 0);
            //树是不断减小的 缩小的范围有 i 决定， 0：只交换第一个元素
            heapify(tree, i, 0);
        }

    }

}
